/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/subarray-sum-closest
   @Language: C++
   @Datetime: 16-02-09 08:38
   */

class Solution {
public:
	/*
	 * @param nums: A list of integers
	 * @return: A list of integers includes the index of the first number and the index of the last number
	 */
	vector<int> subarraySumClosest(vector<int> &nums) {
		// write your code here
		if(nums.size()<2) return {0,0};
		map<int,int> sums;     // sum, index
		for(int i=0, sum=0; i<nums.size(); ++i){
			sum+=nums[i];
			if (sums.find(sum)!=sums.end()) return {sums[sum]+1,i};
			sums[sum]=i;
		}

		map<int,int>::iterator i,j;
		int sum=INT_MAX, diff=0;
		vector<int> v={0,0};
		for(i=j=sums.begin(); ++i!=sums.end(); j=i){
			diff=abs(i->first - j->first);
			if (diff<sum){
				v[0]=min(i->second,j->second)+1;
				v[1]=max(i->second,j->second);
				sum=diff;
			}
		}
		return v;
	}
};
